package com.LeeCode;

/**
 * 得分最高的单词集合
 */

public class Code1255 {
    public static void main(String[] args) {
        String[] words = {"dog", "cat", "dad", "good"};
        char[] letters = {'a', 'a', 'c', 'd', 'd', 'd', 'g', 'o', 'o'};
        int[] score = {1, 0, 9, 5, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

        System.out.println(new Code1255().maxScoreWords(words, letters, score));
    }

    private int ans = 0;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] cnt = new int[26];
        for (char c : letters) {
            cnt[c - 'a']++;
        }
        int[] cur = new int[26];
        backtrace(words, 0, cur, cnt, score);
        return ans;
    }

    private void backtrace(String[] words, int index, int[] cur, int[] cnt, int[] score) {
        if (index == words.length) {
            int s = 0;
            for (int i = 0; i < 26; i++) {
                s += cur[i] * score[i];
            }
            ans = Math.max(ans, s);
            return;
        }
        backtrace(words, index + 1, cur, cnt, score);

        if (check(words[index], cur, cnt)) {
            for (char c : words[index].toCharArray()) {
                cur[c - 'a']++;
            }
            backtrace(words, index + 1, cur, cnt, score);
            for (char c : words[index].toCharArray()) {
                cur[c - 'a']--;
            }
        }
    }

    private boolean check(String word, int[] cur, int[] cnt) {
        int[] temp = new int[26];
        for (char c : word.toCharArray()) {
            temp[c - 'a']++;
            if (temp[c - 'a'] + cur[c - 'a'] > cnt[c - 'a']) return false;
        }
        return true;
    }

}
